Alpha–beta pruning is a vaiant of minimax search for zero-sum two player games. It adopts a similar insight to branch and bound for simple tree search. As there are two players, it keeps a 'best so far' value for each player. By convention alpha is the best for the first player and beta for the second, but these swop as one moves down the game tree alernating the players' turns. Imagine the frist player has exmaind a numer of possible moves and has a best so far move with score 10. It starts to explore a new move M and looks at the second player's options. As soon as it encounters one with the second player's score greater than -10 (so first player worse than 10), it can prune the whole of the branch associated with M as it is clearly less good thath best so far move. A similar strategy is used recursively but alternating 'best so far' roles. Note, like minimax, alpha–beta pruning assumes a perfect opponent.
Defined on pages 228, 229
Used on pages 221, 228, 229, 232, 238
Also known as alpha-beta search, alpha–beta